Search Results

Documents authored by Chen, Shiping


Document
Artifact
Flow-Sensitive Type-Based Heap Cloning (Artifact)

Authors: Mohamad Barbar, Yulei Sui, and Shiping Chen

Published in: DARTS, Volume 6, Issue 2, Special Issue of the 34th European Conference on Object-Oriented Programming (ECOOP 2020)


Abstract
This artifact contains our implementation of a new flow-sensitive type-based points-to analysis, described in "Flow-Sensitive Type-Based Heap Cloning" by Mohamad Barbar, Yulei Sui, and Shiping Chen (ECOOP 2020). This analysis performs heap cloning based on C and C++ types rather than calling contexts. Packaged as a Docker image, the artifact allows users to reproduce the claims made in the "Evaluation" section of the associated paper (Section 5.2) and to build and analyse arbitrary software.

Cite as

Mohamad Barbar, Yulei Sui, and Shiping Chen. Flow-Sensitive Type-Based Heap Cloning (Artifact). In Special Issue of the 34th European Conference on Object-Oriented Programming (ECOOP 2020). Dagstuhl Artifacts Series (DARTS), Volume 6, Issue 2, pp. 1:1-1:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@Article{barbar_et_al:DARTS.6.2.1,
  author =	{Barbar, Mohamad and Sui, Yulei and Chen, Shiping},
  title =	{{Flow-Sensitive Type-Based Heap Cloning (Artifact)}},
  pages =	{1:1--1:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2020},
  volume =	{6},
  number =	{2},
  editor =	{Barbar, Mohamad and Sui, Yulei and Chen, Shiping},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.6.2.1},
  URN =		{urn:nbn:de:0030-drops-131988},
  doi =		{10.4230/DARTS.6.2.1},
  annote =	{Keywords: Heap cloning, type-based analysis, flow-sensitivity}
}
Document
Flow-Sensitive Type-Based Heap Cloning

Authors: Mohamad Barbar, Yulei Sui, and Shiping Chen

Published in: LIPIcs, Volume 166, 34th European Conference on Object-Oriented Programming (ECOOP 2020)


Abstract
By respecting program control-flow, flow-sensitive pointer analysis promises more precise results than its flow-insensitive counterpart. However, existing heap abstractions for C and C++ flow-sensitive pointer analyses model the heap by creating a single abstract heap object for each memory allocation. Two runtime heap objects which originate from the same allocation site are imprecisely modelled using one abstract object, which makes them share the same imprecise points-to sets and thus reduces the benefit of analysing heap objects flow-sensitively. On the other hand, equipping flow-sensitive analysis with context-sensitivity, whereby an abstract heap object would be created (cloned) per calling context, can yield a more precise heap model, but at the cost of uncontrollable analysis overhead when analysing larger programs. This paper presents TypeClone, a new type-based heap model for flow-sensitive analysis. Our key insight is to differentiate concrete heap objects lazily using type information at use sites within the program control-flow (e.g., when accessed via pointer dereferencing) for programs which conform to the strict aliasing rules set out by the C and C++ standards. The novelty of TypeClone lies in its lazy heap cloning: an untyped abstract heap object created at an allocation site is killed and replaced with a new object (i.e. a clone), uniquely identified by the type information at its use site, for flow-sensitive points-to propagation. Thus, heap cloning can be performed within a flow-sensitive analysis without the need for context-sensitivity. Moreover, TypeClone supports new kinds of strong updates for flow-sensitive analysis where heap objects are filtered out from imprecise points-to relations at object use sites according to the strict aliasing rules. Our method is neither strictly superior nor inferior to context-sensitive heap cloning, but rather, represents a new dimension that achieves a sweet spot between precision and efficiency. We evaluate our analysis by comparing TypeClone with state-of-the-art sparse flow-sensitive points-to analysis using the 12 largest programs in GNU Coreutils. Our experimental results also confirm that TypeClone is more precise than flow-sensitive pointer analysis and is able to, on average, answer over 15% more alias queries with a no-alias result.

Cite as

Mohamad Barbar, Yulei Sui, and Shiping Chen. Flow-Sensitive Type-Based Heap Cloning. In 34th European Conference on Object-Oriented Programming (ECOOP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 166, pp. 24:1-24:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{barbar_et_al:LIPIcs.ECOOP.2020.24,
  author =	{Barbar, Mohamad and Sui, Yulei and Chen, Shiping},
  title =	{{Flow-Sensitive Type-Based Heap Cloning}},
  booktitle =	{34th European Conference on Object-Oriented Programming (ECOOP 2020)},
  pages =	{24:1--24:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-154-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{166},
  editor =	{Hirschfeld, Robert and Pape, Tobias},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2020.24},
  URN =		{urn:nbn:de:0030-drops-131819},
  doi =		{10.4230/LIPIcs.ECOOP.2020.24},
  annote =	{Keywords: Heap cloning, type-based analysis, flow-sensitivity}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail